package mao.leetcode.others.leetcode106;

import java.util.HashMap;
import java.util.Map;

public class Solution {

    private static Map<Integer, Integer> map = new HashMap<>();  //节约每次查找的时间


    public  static TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) return null;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
         return helper(postorder,0,postorder.length-1,0);
    }

    //startIn 是为了避免数组由于后续遍历产生偏移而设计的。
    public static TreeNode helper(int[] preorder, int startPost,int endPost,int startIn) {
        if (startPost > endPost) return null;
        if (startPost == endPost) return new TreeNode(preorder[endPost]);
        TreeNode root = new TreeNode(preorder[endPost]);
        int i = map.get(preorder[endPost]);
        int bais = i-startIn;
        root.left = helper(preorder,startPost,startPost+bais-1,startIn);  //对于前序遍历数组需要考虑数组的偏移
        root.right = helper(preorder,bais+startPost,endPost-1,i+1);
        return root;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
